package com.sicheng.lc.周赛.分类.前缀和or差分数组;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/22 13:15
 */
@SuppressWarnings("all")
public class 转角路径的乘积中最多能有几个尾随零 {
    //https://leetcode.cn/problems/maximum-trailing-zeros-in-a-cornered-path/
    // 二维矩阵常常使用某个方向的压缩变成一维形式
    // 只有出现2,5才能出现后缀0
    // 每个数据grid[i,j] <=1000, 直接预处理1000以内所有数的2,5的个数
    // 预处理前缀和
    // 列方向，行方向 处理2，5的个数的前缀和
    public int maxTrailingZeros(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 列方向前缀和数组 存2,5的个数
        int[][][] a = new int[m + 1][n + 1][2];
        // 行方向前缀和数组
        int[][][] b = new int[m + 1][n + 1][2];
        // 1000以内所有数的2,5个数
        int[][] nums = new int[1001][2];
        for (int i = 2; i < nums.length; i++) {
            int x = i;
            while (x % 2 == 0) {
                x >>= 1;
                nums[i][0]++;
            }

            while (x % 5 == 0) {
                x /= 5;
                nums[i][1]++;
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int x = grid[j - 1][i - 1];
                a[j][i][0] = a[j - 1][i][0] + nums[x][0];
                a[j][i][1] = a[j - 1][i][1] + nums[x][1];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int x = grid[i - 1][j - 1];
                b[i][j][0] = b[i][j - 1][0] + nums[x][0];
                b[i][j][1] = b[i][j - 1][1] + nums[x][1];
            }
        }


        int x = -1;
        if (m < n)
            x = get1(m, n, a, b);
        else
            x = get2(m, n, a, b);

        return x;
    }

    //复杂度 n*m*m
    //枚举行 固定列
    private int get1(int m, int n, int[][][] a, int[][][] b) {
        int x = -1;
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= m; i++) {
                for (int j = i; j <= m; j++) {
                    int c2 = a[j][k][0] - a[i - 1][k][0];
                    int c5 = a[j][k][1] - a[i - 1][k][1];
                    int d1 = Math.min(c2 + b[j][k - 1][0], c5 + b[j][k - 1][1]);
                    int d2 = Math.min(c2 + b[i][k - 1][0], c5 + b[i][k - 1][1]);
                    int d3 = Math.min(c2 + b[i][n][0] - b[i][k][0], c5 + b[i][n][1] - b[i][k][1]);
                    int d4 = Math.min(c2 + b[j][n][0] - b[j][k][0], c5 + b[j][n][1] - b[j][k][1]);
                    x = max(d3, d4, d1, d2, x);
                }
            }
        }
        return x;
    }

    //复杂度 n*n*m
    // 枚举列 固定行
    private int get2(int m, int n, int[][][] a, int[][][] b) {
        int x = -1;
        for (int k = 1; k <= m; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = i; j <= n; j++) {
                    int c2 = b[k][i][0];
                    int c5 = b[k][i][1];
                    int d1 = Math.min(c2 + a[k - 1][i][0], c5 + a[k - 1][i][1]);
                    int d2 = Math.min(c2 + a[m][i][0] - a[k][i][0], c5 + a[m][i][1] - a[k][i][1]);

                    c2 = b[k][j][0];
                    c5 = b[k][j][1];
                    int d3 = Math.min(c2 + a[k - 1][j][0], c5 + a[k - 1][j][1]);
                    int d4 = Math.min(c2 + a[m][j][0] - a[k][j][0], c5 + a[m][j][1] - a[k][j][1]);
                    x = max(d3, d4, d1, d2, x);

                    c2 = b[k][n][0] - b[k][i - 1][0];
                    c5 = b[k][n][1] - b[k][i - 1][1];
                    d1 = Math.min(c2 + a[k - 1][i][0], c5 + a[k - 1][i][1]);
                    d2 = Math.min(c2 + a[m][i][0] - a[k][i][0], c5 + a[m][i][1] - a[k][i][1]);

                    c2 = b[k][n][0] - b[k][j - 1][0];
                    c5 = b[k][n][1] - b[k][j - 1][1];
                    d3 = Math.min(c2 + a[k - 1][j][0], c5 + a[k - 1][j][1]);
                    d4 = Math.min(c2 + a[m][j][0] - a[k][j][0], c5 + a[m][j][1] - a[k][j][1]);
                    x = max(d3, d4, d1, d2, x);
                }
            }
        }
        return x;
    }


    int max(int... x) {
        int[] y = x;
        int max = -1;
        for (int i = 0; i < y.length; i++) {
            max = Math.max(y[i], max);
        }
        return max;
    }

    public static void main(String[] args) {
        转角路径的乘积中最多能有几个尾随零 solution = new 转角路径的乘积中最多能有几个尾随零();
        int[][] g = {
                {824, 709, 193, 413, 701, 836, 727},
                {135, 844, 599, 211, 140, 933, 205},
                {329, 68, 285, 282, 301, 387, 231},
                {293, 210, 478, 352, 946, 902, 137},
                {806, 900, 290, 636, 589, 522, 611},
                {450, 568, 990, 592, 992, 128, 92},
                {780, 653, 795, 457, 980, 942, 927},
                {849, 901, 604, 906, 912, 866, 688}
        };
        int[][] g1 = {
                {534, 575, 625, 84, 20, 999, 35},
                {208, 318, 96, 380, 819, 102, 669}
        };
        System.out.println(solution.maxTrailingZeros(g1));
    }
}

